package SubjectTree.Four;

import java.util.Deque;
import java.util.LinkedList;

import Utility.TreeNode;

public class IsValidBST {

/**
 * 难度：中等
 * 
 * 98. 验证二叉搜索树
 * 	给定一个二叉树，判断其是否是一个有效的二叉搜索树。
 * 	假设一个二叉搜索树具有如下特征：
 * 		节点的左子树只包含小于当前节点的数。
 * 		节点的右子树只包含大于当前节点的数。
 * 		所有左子树和右子树自身必须也是二叉搜索树。
 * 	
 * 示例 1:
 * 	输入:
 * 	    2
 * 	   / \
 * 	  1   3
 * 	输出: true
 * 	
 * 示例 2:
 * 	输入:
 * 	    5
 * 	   / \
 * 	  1   4
 * 	     / \
 * 	    3   6
 * 	输出: false
 * 	解释: 输入为: [5,1,4,null,null,3,6]。
 * 	     根节点的值为 5 ，但是其右子节点值为 4 。
 *
 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		IsValidBST ivbst = new IsValidBST();
		System.out.println(ivbst.isValidBST_1(TreeNode.MkTree("[2,1,3]")));
	}
	//自己写(中序遍历)
	public boolean isValidBST(TreeNode root) {
		Deque<TreeNode> deque = new LinkedList<>();
		TreeNode pre = null;
		while(!deque.isEmpty()||root!=null) {
			while(root!=null) {
				deque.push(root);
				root = root.left;
			}
			root = deque.pop();
			if(pre!=null && root.val<=pre.val)return false;
			pre = root;//保存前一个访问的结点
			
			root = root.right;
			
		}
		return true;
    }
	//自己写(递归)
	TreeNode pre = null;
	public boolean isValidBST_1(TreeNode root) {
		if(root == null) return true;
		boolean left = isValidBST_1(root.left);
		
		if(pre!=null && pre.val>=root.val)return false;
		pre = root;// 记录前一个节点
		
		boolean right = isValidBST_1(root.right);
		return left && right;
    }
	
	//方法一: 递归
	public boolean isValidBST1(TreeNode root) {
        return helper(root, null, null);
    }
	//lower左值,upper右值
    public boolean helper(TreeNode node, Integer lower, Integer upper) {
        if (node == null) {
            return true;
        }

        int val = node.val;
        if (lower != null && val <= lower) {
            return false;
        }
        if (upper != null && val >= upper) {
            return false;
        }

        if (!helper(node.right, val, upper)) {
            return false;
        }
        if (!helper(node.left, lower, val)) {
            return false;
        }
        return true;
    }
    //方法二：中序遍历
    public boolean isValidBST2(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        double inorder = -Double.MAX_VALUE;

        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
              // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
            if (root.val <= inorder) {
                return false;
            }
            inorder = root.val;
            root = root.right;
        }
        return true;
    }
}
